package interview.i_001_algorithm;

import lombok.NoArgsConstructor;

/**
 * 链表反转
 */
public class T003_LinkedList {

    public static void main(String[] args) {
        T003_LinkedList linkedList = new T003_LinkedList();
        for (int i = 0; i < 5; i++) {
            linkedList.addHeadNode(new Node(i));
        }
        System.out.println(linkedList);
        linkedList.reverse();
        System.out.println(linkedList);
    }

    @NoArgsConstructor
    static class Node {
        Node next;
        Object data;

        public Node(Object data) {
            this.data = data;
        }
    }

    Node head;

    public T003_LinkedList() {
        head = new Node();
        head.next = null;
    }

    public void addHeadNode(Node node) {
        node.next = head.next;
        head.next = node;
    }

    public void removeNode(Node node) {
        if (node.next == null) {
            node = head;
            while (node.next.next != null) {
                node = node.next;
            }
            if (node == head) { // 只有两个节点
                head.next = null;
                return;
            }
        }
        node.data = node.next.data;
        node.next = node.next.next;
    }

    public void reverse() {
        if (head.next == null) {
            return;
        }
        reverse(head.next);
    }

    public Node reverse(Node curr) {
        if (curr.next == null) { // 是最后一个节点
            head.next = curr;
            return curr;
        }
        Node prev = reverse(curr.next);
        prev.next = curr;
        curr.next = null;
        return curr;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node node = head.next;
        while (node != null && node.data != null) {
            sb.append(node.data).append("\t");
            node = node.next;
        }
        return sb.toString();
    }
}
